(王道计算机组成原理)第七章输入和输出系统

ITS_Oaij: 个人学习笔记（B+树 vs B树）： 1）B+树内节点不存储数据，所有data存储在叶子节点导致查询时间复杂度固定为logn。 2）B-树查询时间复杂度不固定，与Key在树中的位置有关，最好为O(1)。

ITS_Oaij: （B树删除）： 终端（低于下限）：兄弟够借（后继+后继的后继/前…+…）；兄弟不够借（双亲+兄弟/注意向上继续合并）。 非终端：用直接前驱/后继代替，转换为终端结点的删除。

ITS_Oaij: 个人学习笔记（B树插入）： 新元素插入时，首先插入到底层的“终端节点”，再向上进行分裂操作（插入位置是通过类似查找确认）。 若插入超出m-1个关键字，需要进行分裂，且是向上分裂。

ITS_Oaij: 个人学习笔记（关于查找效率分析）： 用顺序查找索引表，ASL最小情况是s=根号n时，为根号n +1。 用折半查找（了解）

ITS_Oaij: 个人学习笔记（折半查找）： 折半查找，又称“二分查找”，仅适用于有序的顺序表。 顺序表其实就是说些元素得是用数组存放起来的，只有顺序表才拥有随机访问的特性，链表没有。